package com.ds.seqlist.LeetCode;

public class Num92_ReverseBetween {
    //    public ListNode reverseBetween(ListNode head, int left, int right) {
//        ListNode dummyHead = new ListNode();
//        dummyHead.next = head;
//        // prev指向带反转区间的前驱节点
//        ListNode prev = dummyHead;
//        // cur指向待反转区间的第一个节点
//        ListNode cur = prev.next;
//        // 先让prev和cur走left - 1步走到对应位置
//        for (int i = 0; i < left - 1; i++) {
//            prev = prev.next;
//            cur = cur.next;
//        }
//        // 只需要反转right - left次即可
//        for (int i = 0; i < right - left; i++) {
//            // 下一个要处理的节点
//            ListNode next = cur.next;
//            // 先删除next，在头插到prev的后面
//            cur.next = next.next;
//            // 头插
//            next.next = prev.next;
//            prev.next = next;
//        }
//        return dummyHead.next;
//    }
    // 反转区间right的后继节点
    ListNode sucessor = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 这就是前right个节点的反转
            return reverseN(head,right);
        }
        // 此时head一定不是待反转的节点,区间的起始和终止节点都-1，head不处理
        head.next = reverseBetween(head.next,left - 1,right - 1);
        return head;
    }

    public ListNode reverseN(ListNode head,int n)  {
        // n = 1
        if (n == 1) {
            sucessor = head.next;
            return head;
        }
        ListNode next = head.next;
        // 第二个节点开始的反转操作交给子函数,头节点自己处理，子函数就少处理一个
        ListNode newHead = reverseN(head.next,n - 1);
        next.next = head;
        head.next = sucessor;
        return newHead;
    }

}
